package cn.bouncyslime.dataStructures.tree.traverseBinaryTree;

import cn.bouncyslime.dataStructures.tree.node.Node;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 先序遍历二叉树
 * @author bouncyslime
 * @date 2021/1/17
 */
public class BinaryTreeTraversing_DLR implements BinaryTreeTraversing{

    /**
     * 递归先序遍历二叉树
     * @param root 二叉树根结点
     */
    public <T> void traverseRecursively(Node<T> root){
        if (root != null) {
            System.out.print(root.getData() + " | ");
            if (root.getLeft() != null){
                traverseRecursively(root.getLeft());
            }
            if (root.getRight() != null) {
                traverseRecursively(root.getRight());
            }
        }
    }

    /**
     * 利用栈迭代先序遍历二叉树
     * @param root 二叉树根结点
     */
    public <T> void traverseIteratively(Node<T> root){
        Deque<Node<T>> stack = new LinkedList<>();
        Node<T> node = root;
        while(node != null || !stack.isEmpty()){
            if(node != null){
                System.out.print(node.getData() + " | ");
                stack.push(node);
                node = node.getLeft();
            }else{
                node = stack.pop();
                node = node.getRight();
            }
        }
    }

    /**
     * 利用栈迭代先序遍历二叉树
     * @param root 二叉树根结点
     */
    public <T> void traverseIteratively2(Node<T> root){
        Deque<Node<T>> stack = new LinkedList<>();
        Node<T> node = root;
        stack.push(node);
        while (!stack.isEmpty()){
            while ((node = stack.peek()) != null) {
                System.out.print(node.getData() + " | ");
                stack.push(node.getLeft());
            }
            stack.pop();
            if (!stack.isEmpty()){
                node = stack.pop();
                stack.push(node.getRight());
            }

        }
    }

    public static void main(String[] args) {
        BinaryTreeTraversing binaryTreeTraversing = new BinaryTreeTraversing_DLR();

        String[] array = {"1", "2", "3", "4", "5", null, null, null, null, "6", "7"};
        Node<String> root = BinaryTreeUtils.createBinaryTreeFromArray(array);
        binaryTreeTraversing.traverseRecursively(root);
        System.out.println();
        binaryTreeTraversing.traverseIteratively(root);
        System.out.println();
        binaryTreeTraversing.traverseIteratively2(root);
    }
}
